home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2004 April / Gamestar_61_2004-04_dvdb.iso / DVDStar / Editace / hltp.exe / {app} / Source Code / Zoners Half-Life Tools / hlrad / sparse.cpp < prev    next >
C/C++ Source or Header  |  2002-12-09  |  15KB  |  570 lines
  1. #include "qrad.h"
  2.  
  3. // Transparency array
  4.  
  5. #ifdef HLRAD_HULLU
  6.  
  7. typedef struct {
  8.     unsigned x;
  9.     unsigned y;
  10.     vec3_t transparency;
  11. } transparency_t;
  12. static transparency_t *s_transparency_list=NULL;
  13. static unsigned long s_transparency_count=0;
  14. static unsigned long s_max_transparency_count=0;
  15.  
  16. static void FindOpacity(const unsigned p1, const unsigned p2, vec3_t &out)
  17. {
  18.     for(unsigned long i = 0; i < s_transparency_count; i++)
  19.     {
  20.         if(s_transparency_list[i].x==p1 && s_transparency_list[i].y==p2)
  21.         {
  22.             VectorCopy(s_transparency_list[i].transparency, out);
  23.             return;
  24.         }
  25.     }
  26.     VectorFill(out, 1.0);
  27. }
  28.  
  29. #endif /*HLRAD_HULLU*/
  30.  
  31.  
  32. typedef struct
  33. {
  34.     unsigned        offset:24;
  35.     unsigned        values:8;
  36. }
  37. sparse_row_t;
  38.  
  39. typedef struct
  40. {
  41.     sparse_row_t*   row;
  42.     int             count;
  43. }
  44. sparse_column_t;
  45.  
  46. sparse_column_t* s_vismatrix;
  47.  
  48. // Vismatrix protected
  49. static unsigned IsVisbitInArray(const unsigned x, const unsigned y)
  50. {
  51.     int             first, last, current;
  52.     int             y_byte = y / 8;
  53.     sparse_row_t*  row;
  54.     sparse_column_t* column = s_vismatrix + x;
  55.  
  56.     if (!column->count)
  57.     {
  58.         return -1;
  59.     }
  60.  
  61.     first = 0;
  62.     last = column->count - 1;
  63.  
  64.     //    Warning("Searching . . .");
  65.     // binary search to find visbit
  66.     while (1)
  67.     {
  68.         current = (first + last) / 2;
  69.         row = column->row + current;
  70.         //        Warning("first %u, last %u, current %u, row %p, row->offset %u", first, last, current, row, row->offset);
  71.         if ((row->offset) < y_byte)
  72.         {
  73.             first = current + 1;
  74.         }
  75.         else if ((row->offset) > y_byte)
  76.         {
  77.             last = current - 1;
  78.         }
  79.         else
  80.         {
  81.             return current;
  82.         }
  83.         if (first > last)
  84.         {
  85.             return -1;
  86.         }
  87.     }
  88. }
  89.  
  90. // Vismatrix protected
  91. static void     InsertVisbitIntoArray(const unsigned x, const unsigned y)
  92. {
  93.     unsigned        count;
  94.     unsigned        y_byte = y / 8;
  95.     sparse_column_t* column = s_vismatrix + x;
  96.     sparse_row_t*   row = column->row;
  97.  
  98.     if (!column->count)
  99.     {
  100.         column->count++;
  101.         row = column->row = (sparse_row_t*)malloc(sizeof(sparse_row_t));
  102.         row->offset = y_byte;
  103.         row->values = 1 << (y & 7);
  104.         return;
  105.     }
  106.  
  107.     // Insertion
  108.     count = 0;
  109.     while (count < column->count)
  110.     {
  111.         if (row->offset > y_byte)
  112.         {
  113.             unsigned        newsize = (column->count + 1) * sizeof(sparse_row_t);
  114.             sparse_row_t*   newrow = (sparse_row_t*)malloc(newsize);
  115.  
  116.             memcpy(newrow, column->row, count * sizeof(sparse_row_t));
  117.             memcpy(newrow + count + 1, column->row + count, (column->count - count) * sizeof(sparse_row_t));
  118.  
  119.             row = newrow + count;
  120.             row->offset = y_byte;
  121.             row->values = 1 << (y & 7);
  122.  
  123.             free(column->row);
  124.             column->row = newrow;
  125.             column->count++;
  126.             return;
  127.         }
  128.  
  129.         row++;
  130.         count++;
  131.     }
  132.  
  133.     // Append
  134.     {
  135.         unsigned        newsize = (count + 1) * sizeof(sparse_row_t);
  136.         sparse_row_t*   newrow = (sparse_row_t*)malloc(newsize);
  137.  
  138.         memcpy(newrow, column->row, column->count * sizeof(sparse_row_t));
  139.  
  140.         row = newrow + column->count;
  141.         row->offset = y_byte;
  142.         row->values = 1 << (y & 7);
  143.  
  144.         free(column->row);
  145.         column->row = newrow;
  146.         column->count++;
  147.         return;
  148.     }
  149. }
  150.  
  151. // Vismatrix public
  152. static void     SetVisBit(unsigned x, unsigned y)
  153. {
  154.     unsigned        offset;
  155.  
  156.     if (x == y)
  157.     {
  158.         return;
  159.     }
  160.  
  161.     if (x > y)
  162.     {
  163.         const unsigned a = x;
  164.         const unsigned b = y;
  165.         x = b;
  166.         y = a;
  167.     }
  168.  
  169.     if (x > g_num_patches)
  170.     {
  171.         Warning("in SetVisBit(), x > num_patches");
  172.     }
  173.     if (y > g_num_patches)
  174.     {
  175.         Warning("in SetVisBit(), y > num_patches");
  176.     }
  177.  
  178.     ThreadLock();
  179.  
  180.     if ((offset = IsVisbitInArray(x, y)) != -1)
  181.     {
  182.         s_vismatrix[x].row[offset].values |= 1 << (y & 7);
  183.     }
  184.     else
  185.     {
  186.         InsertVisbitIntoArray(x, y);
  187.     }
  188.  
  189.     ThreadUnlock();
  190. }
  191.  
  192. // Vismatrix public
  193. #ifdef HLRAD_HULLU
  194. static bool     CheckVisBitSparse(unsigned x, unsigned y, vec3_t &transparency_out)
  195. #else
  196. static bool     CheckVisBitSparse(unsigned x, unsigned y)
  197. #endif
  198. {
  199.     unsigned        offset;
  200.  
  201.     if (x == y)
  202.     {
  203. #ifdef HLRAD_HULLU
  204.         VectorFill(transparency_out, 1.0);
  205. #endif
  206.         return 1;
  207.     }
  208.  
  209.     if (x > y)
  210.     {
  211.         const unsigned a = x;
  212.         const unsigned b = y;
  213.         x = b;
  214.         y = a;
  215.     }
  216.  
  217.     if (x > g_num_patches)
  218.     {
  219.         Warning("in CheckVisBit(), x > num_patches");
  220.     }
  221.     if (y > g_num_patches)
  222.     {
  223.         Warning("in CheckVisBit(), y > num_patches");
  224.     }
  225.  
  226.     if ((offset = IsVisbitInArray(x, y)) != -1)
  227.     {
  228. #ifdef HLRAD_HULLU
  229.         if(g_customshadow_with_bouncelight)
  230.         {
  231.              vec3_t tmp = {1.0, 1.0, 1.0};
  232.              FindOpacity(x, y, tmp);
  233.              VectorCopy(tmp, transparency_out);
  234.         }
  235.         else
  236.         {
  237.              VectorFill(transparency_out, 1.0);
  238.         }
  239. #endif
  240.         return s_vismatrix[x].row[offset].values & (1 << (y & 7));
  241.     }
  242. #ifdef HLRAD_HULLU
  243.     VectorFill(transparency_out, 1.0);
  244. #endif
  245.     return 0;
  246. }
  247.  
  248. /*
  249.  * ==============
  250.  * TestPatchToFace
  251.  * 
  252.  * Sets vis bits for all patches in the face
  253.  * ==============
  254.  */
  255. static void     TestPatchToFace(const unsigned patchnum, const int facenum, const int head)
  256. {
  257.     patch_t*        patch = &g_patches[patchnum];
  258.     patch_t*        patch2 = g_face_patches[facenum];
  259.  
  260.     // if emitter is behind that face plane, skip all patches
  261.  
  262.     if (patch2)
  263.     {
  264.         const dplane_t* plane2 = getPlaneFromFaceNumber(facenum);
  265.  
  266.         if (DotProduct(patch->origin, plane2->normal) > (PatchPlaneDist(patch2) + MINIMUM_PATCH_DISTANCE))
  267.         {
  268.             // we need to do a real test
  269.             const dplane_t* plane = getPlaneFromFaceNumber(patch->faceNumber);
  270.  
  271.             for (; patch2; patch2 = patch2->next)
  272.             {
  273.                 unsigned        m = patch2 - g_patches;
  274.  
  275. #ifdef HLRAD_HULLU
  276.                 vec3_t        transparency = {1.0,1.0,1.0};
  277. #endif
  278.  
  279.                 // check vis between patch and patch2
  280.                 // if bit has not already been set
  281.                 //  && v2 is not behind light plane
  282.                 //  && v2 is visible from v1
  283.                 if (m > patchnum
  284.                     && (DotProduct(patch2->origin, plane->normal) > (PatchPlaneDist(patch) + MINIMUM_PATCH_DISTANCE))
  285.                     && (TestLine_r(head, patch->origin, patch2->origin) == CONTENTS_EMPTY)
  286. #ifdef HLRAD_HULLU
  287.                     && (!TestSegmentAgainstOpaqueList(patch->origin, patch2->origin, transparency)))
  288. #else
  289.                     && (!TestSegmentAgainstOpaqueList(patch->origin, patch2->origin)))
  290. #endif
  291.                 {
  292.                                         
  293. #ifdef HLRAD_HULLU
  294.                     // transparency face fix table
  295.                     if(g_customshadow_with_bouncelight && fabs(VectorAvg(transparency) - 1.0) < 0.001)
  296.                     {
  297.                         while(s_transparency_count>=s_max_transparency_count)
  298.                         {
  299.                             //new size
  300.                             unsigned long oldsize = s_max_transparency_count;
  301.                             s_max_transparency_count += 128;
  302.                             
  303.                             //realloc
  304.                             s_transparency_list = (transparency_t*)realloc(s_transparency_list, s_max_transparency_count * sizeof(transparency_t));
  305.                             
  306.                             // clean new memory
  307.                             memset(&s_transparency_list[oldsize], 0, sizeof(transparency_t) * 128);
  308.                         }
  309.                         
  310.                         //add to array
  311.                         VectorCopy(transparency, s_transparency_list[s_transparency_count].transparency);
  312.                     s_transparency_list[s_transparency_count].y = m;
  313.                         s_transparency_list[s_transparency_count].x = patchnum;
  314.                         
  315.                         s_transparency_count++;
  316.                     }
  317. #endif
  318.                     SetVisBit(m, patchnum);
  319.                 }
  320.             }
  321.         }
  322.     }
  323. }
  324.  
  325. /*
  326.  * ==============
  327.  * BuildVisRow
  328.  * 
  329.  * Calc vis bits from a single patch
  330.  * ==============
  331.  */
  332. static void     BuildVisRow(const int patchnum, byte* pvs, const int head)
  333. {
  334.     int             j, k, l;
  335.     byte            face_tested[MAX_MAP_FACES];
  336.     dleaf_t*        leaf;
  337.  
  338.     memset(face_tested, 0, g_numfaces);
  339.  
  340.     // leaf 0 is the solid leaf (skipped)
  341.     for (j = 1, leaf = g_dleafs + 1; j < g_numleafs; j++, leaf++)
  342.     {
  343.         if (!(pvs[(j - 1) >> 3] & (1 << ((j - 1) & 7))))
  344.         {
  345.             continue;                                      // not in pvs
  346.         }
  347.         for (k = 0; k < leaf->nummarksurfaces; k++)
  348.         {
  349.             l = g_dmarksurfaces[leaf->firstmarksurface + k];
  350.  
  351.             // faces can be marksurfed by multiple leaves, but
  352.             // don't bother testing again
  353.             if (face_tested[l])
  354.                 continue;
  355.             face_tested[l] = 1;
  356.  
  357.             TestPatchToFace(patchnum, l, head);
  358.         }
  359.     }
  360. }
  361.  
  362. /*
  363.  * ===========
  364.  * BuildVisLeafs
  365.  * 
  366.  * This is run by multiple threads
  367.  * ===========
  368.  */
  369. #ifdef SYSTEM_WIN32
  370. #pragma warning(push)
  371. #pragma warning(disable: 4100)                             // unreferenced formal parameter
  372. #endif
  373. static void     BuildVisLeafs(int threadnum)
  374. {
  375.     int             i;
  376.     int             lface, facenum, facenum2;
  377.     byte            pvs[(MAX_MAP_LEAFS + 7) / 8];
  378.     dleaf_t*        srcleaf;
  379.     dleaf_t*        leaf;
  380.     patch_t*        patch;
  381.     int             head;
  382.     unsigned        patchnum;
  383.  
  384.     while (1)
  385.     {
  386.         //
  387.         // build a minimal BSP tree that only
  388.         // covers areas relevent to the PVS
  389.         //
  390.         i = GetThreadWork();
  391.         if (i == -1)
  392.         {
  393.             break;
  394.         }
  395.         i++;                                               // skip leaf 0
  396.         srcleaf = &g_dleafs[i];
  397.         DecompressVis(&g_dvisdata[srcleaf->visofs], pvs, sizeof(pvs));
  398.         head = 0;
  399.  
  400.         //
  401.         // go through all the faces inside the
  402.         // leaf, and process the patches that
  403.         // actually have origins inside
  404.         //
  405.         for (lface = 0; lface < srcleaf->nummarksurfaces; lface++)
  406.         {
  407.             facenum = g_dmarksurfaces[srcleaf->firstmarksurface + lface];
  408.             for (patch = g_face_patches[facenum]; patch; patch = patch->next)
  409.             {
  410.                 leaf = PointInLeaf(patch->origin);
  411.                 if (leaf != srcleaf)
  412.                 {
  413.                     continue;
  414.                 }
  415.  
  416.                 patchnum = patch - g_patches;
  417.                 // build to all other world leafs
  418.                 BuildVisRow(patchnum, pvs, head);
  419.  
  420.                 // build to bmodel faces
  421.                 if (g_nummodels < 2)
  422.                 {
  423.                     continue;
  424.                 }
  425.                 for (facenum2 = g_dmodels[1].firstface; facenum2 < g_numfaces; facenum2++)
  426.                 {
  427.                     TestPatchToFace(patchnum, facenum2, head);
  428.                 }
  429.             }
  430.         }
  431.  
  432.     }
  433. }
  434.  
  435. #ifdef SYSTEM_WIN32
  436. #pragma warning(pop)
  437. #endif
  438.  
  439. /*
  440.  * ==============
  441.  * BuildVisMatrix
  442.  * ==============
  443.  */
  444. static void     BuildVisMatrix()
  445. {
  446.     s_vismatrix = (sparse_column_t*)AllocBlock(g_num_patches * sizeof(sparse_column_t));
  447.  
  448.     if (!s_vismatrix)
  449.     {
  450.         Log("Failed to allocate vismatrix");
  451.         hlassume(s_vismatrix != NULL, assume_NoMemory);
  452.     }
  453.  
  454.     NamedRunThreadsOn(g_numleafs - 1, g_estimate, BuildVisLeafs);
  455. }
  456.  
  457. static void     FreeVisMatrix()
  458. {
  459.     if (s_vismatrix)
  460.     {
  461.         unsigned        x;
  462.         sparse_column_t* item;
  463.  
  464.         for (x = 0, item = s_vismatrix; x < g_num_patches; x++, item++)
  465.         {
  466.             if (item->row)
  467.             {
  468.                 free(item->row);
  469.             }
  470.         }
  471.         if (FreeBlock(s_vismatrix))
  472.         {
  473.             s_vismatrix = NULL;
  474.         }
  475.         else
  476.         {
  477.             Warning("Unable to free vismatrix");
  478.         }
  479.     }
  480.  
  481. #ifdef HLRAD_HULLU
  482.     if(s_transparency_list)
  483.     {
  484.         free(s_transparency_list);
  485.         s_transparency_list = NULL;
  486.     }
  487.     s_transparency_count = s_max_transparency_count = 0;    
  488. #endif
  489.  
  490. }
  491.  
  492. static void     DumpVismatrixInfo()
  493. {
  494.     unsigned        totals[8];
  495.     unsigned        total_vismatrix_memory = sizeof(sparse_column_t) * g_num_patches;
  496.  
  497.     sparse_column_t* column_end = s_vismatrix + g_num_patches;
  498.     sparse_column_t* column = s_vismatrix;
  499.  
  500.     memset(totals, 0, sizeof(totals));
  501.  
  502.     while (column < column_end)
  503.     {
  504.         total_vismatrix_memory += column->count * sizeof(sparse_row_t);
  505.         column++;
  506.     }
  507.  
  508.     Log("%-20s: %5.1f megs\n", "visibility matrix", total_vismatrix_memory / (1024 * 1024.0));
  509. }
  510.  
  511. //
  512. // end old vismat.c
  513. ////////////////////////////
  514.  
  515. void            MakeScalesSparseVismatrix()
  516. {
  517.     char            transferfile[_MAX_PATH];
  518.  
  519.     hlassume(g_num_patches < MAX_SPARSE_VISMATRIX_PATCHES, assume_MAX_PATCHES);
  520.  
  521.     safe_strncpy(transferfile, g_source, _MAX_PATH);
  522.     StripExtension(transferfile);
  523.     DefaultExtension(transferfile, ".inc");
  524.  
  525.     if (!g_incremental || !readtransfers(transferfile, g_num_patches))
  526.     {
  527.         // determine visibility between g_patches
  528.         BuildVisMatrix();
  529.         DumpVismatrixInfo();
  530.         g_CheckVisBit = CheckVisBitSparse;
  531.  
  532. #ifdef HLRAD_HULLU
  533.         if((s_max_transparency_count*sizeof(transparency_t))>=(1024 * 1024))
  534.             Log("%-20s: %5.1f megs\n", "custom shadow array", (s_max_transparency_count*sizeof(transparency_t)) / (1024 * 1024.0));
  535.         else if(s_transparency_count)
  536.             Log("%-20s: %5.1f kilos\n", "custom shadow array", (s_max_transparency_count*sizeof(transparency_t)) / 1024.0);
  537. #endif
  538.         
  539. #ifndef HLRAD_HULLU
  540.         NamedRunThreadsOn(g_num_patches, g_estimate, MakeScales);
  541. #else
  542.     if(g_rgb_transfers)
  543.         {NamedRunThreadsOn(g_num_patches, g_estimate, MakeRGBScales);}
  544.     else
  545.         {NamedRunThreadsOn(g_num_patches, g_estimate, MakeScales);}
  546. #endif
  547.         FreeVisMatrix();
  548.  
  549.         // invert the transfers for gather vs scatter
  550. #ifndef HLRAD_HULLU
  551.         NamedRunThreadsOnIndividual(g_num_patches, g_estimate, SwapTransfers);
  552. #else
  553.     if(g_rgb_transfers)
  554.         {NamedRunThreadsOnIndividual(g_num_patches, g_estimate, SwapRGBTransfers);}
  555.     else
  556.         {NamedRunThreadsOnIndividual(g_num_patches, g_estimate, SwapTransfers);}
  557. #endif
  558.         if (g_incremental)
  559.         {
  560.             writetransfers(transferfile, g_num_patches);
  561.         }
  562.         else
  563.         {
  564.             unlink(transferfile);
  565.         }
  566.         // release visibility matrix
  567.         DumpTransfersMemoryUsage();
  568.     }
  569. }
  570.